package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-03
 */

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
 *
 * 如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。
 */
public class leetcode524 {
    public String findLongestWord(String s, List<String> dictionary) {
        Collections.sort(dictionary, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s2.length()!=s1.length()? s2.length()-s1.length() : s1.compareTo(s2);
            }
        });
        for (String d : dictionary) {
            if (check(d,s)) return d;
        }
        return "";
    }
    //x是字典中的字符串，判断x是不是y的子序列,如果是，则x可以由y删除某些字符得到
    public boolean check(String x,String y){
        int j = 0;
        for (int i = 0;i<y.length() && j<x.length(); i++){
            if (x.charAt(j) == y.charAt(i)) j++;
        }
        return j == x.length();
    }
}
